package com.lw.leetcode.str.c;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2030. 含特定字母的最小子序列
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/7 16:11
 */
public class SmallestSubsequence {

    public static void main(String[] args) {
        SmallestSubsequence test = new SmallestSubsequence();

        // "eet"
//        String s = "leet";
//        int k = 3;
//        char letter = 'e';
//        int repetition = 1;

        // "aba"
//        String s = "bbbabbbbbba";
//        int k = 3;
//        char letter = 'b';
//        int repetition = 1;

        // "zazzzz"
        String s = "zzazzzz";
        int k = 6;
        char letter = 'z';
        int repetition = 4;

        // "ecde"
//        String s = "leetcode";
//        int k = 4;
//        char letter = 'e';
//        int repetition = 2;

        // "eece"
//        String s = "leetcode";
//        int k = 4;
//        char letter = 'e';
//        int repetition = 3;

        // "bb"
//        String s = "bb";
//        int k = 2;
//        char letter = 'b';
//        int repetition = 2;

        String s1 = test.smallestSubsequence(s, k, letter, repetition);
        System.out.println(s1);

    }

    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        int length = s.length();
        if (k == length) {
            return s;
        }
        StringBuilder sb = new StringBuilder(k);
        if (k == repetition) {
            return add(k, letter, sb);
        }
        int[] items = new int[repetition + 1];
        char[] chars = s.toCharArray();
        int no = 0;
        int end = length - 1;
        items[0] = length - 1;
        while (no != repetition) {
            if (chars[end] == letter) {
                items[++no] = end;
            }
            end--;
        }
        end = Math.min(end + 1, length - k);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i <= end; i++) {
            queue.add(((int) chars[i] << 24) + i);
        }
        int st = 0;
        int used = 0;
        while (sb.length() < k) {
            int p = queue.poll();
            char c = (char) (p >> 24);
            int index = p & 0XFFFFFF;
            if (index < st) {
                continue;
            }
            int t = end + 1;
            sb.append(c);
            if (c == letter) {
                used++;
            }
            if (repetition - used == k - sb.length()) {
                return add(k - sb.length(), letter, sb);
            }
            st = index;
            end = Math.min(items[repetition - used < 0 ? 0 : repetition - used], length - k + sb.length());
            for (int i = t; i <= end; i++) {
                queue.add(((int) chars[i] << 24) + i);
            }
        }
        return sb.toString();
    }

    private String add(int n, char c, StringBuilder sb) {
        for (int i = 0; i < n; i++) {
            sb.append(c);
        }
        return sb.toString();
    }

}
